package 二叉树;

import java.util.HashMap;
import java.util.Map;

public class No662二叉树最大宽度 {

    /**
     * 给定一个二叉树，编写一个函数来获取这个树的最大宽度。
     * 树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
     * 每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
     *
     * 示例 1:
     * 输入:
     *
     *            1
     *          /   \
     *         3     2
     *        / \     \
     *       5   3     9
     *
     * 输出: 4
     * 解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。
     * 示例 2:
     * 输入:
     *
     *           1
     *          /
     *         3
     *        / \
     *       5   3
     *
     * 输出: 2
     * 解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。
     * 示例 3:
     * 输入:
     *
     *           1
     *          / \
     *         3   2
     *        /
     *       5
     *
     * 输出: 2
     * 解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。
     * 示例 4:
     * 输入:
     *
     *           1
     *          / \
     *         3   2
     *        /     \
     *       5       9
     *      /         \
     *     6           7
     * 输出: 8
     * 解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。
     * 注意: 答案在32位有符号整数的表示范围内。
     */

    private int result;
    //越小越好
    private Map<Integer,Integer> leftStartWhitDeep=new HashMap<>();

    /**
     * 注意题目所说的满二叉树
     * left=root*2 right=root*2+1
     */
    public int widthOfBinaryTree(TreeNode root) {
        dfs(root,1,0);
        return result;
    }

    private void dfs(TreeNode node,int deep,int index) {

        if(node==null){
            return;
        }

        //没有就先放入,因为左先,所以第一次放的必定是最左边
        leftStartWhitDeep.putIfAbsent(deep,index);

        //可以开始进行比较了,无需判空,因为有本身在
        result=Math.max(result,index-leftStartWhitDeep.get(deep)+1);

        dfs(node.left,deep+1,index*2);
        dfs(node.right,deep+1,index*2+1);

    }

}
